The present invention relates to a method of and an apparatus for searching a Contents Addressable Memory (hereafter abbreviated as the CAM) which can be accessed with its contents, that is, memorized data, as a search key.
In the CAM, data memorized therein can be accessed with contents of the data themselves, while, in ordinary memory devices, memorized data are simply to be accessed with their addresses. That is, when a bit sequence of a word length, whereof some bits may be masked, is given as a search key to the CAM in a search mode, the CAM outputs an address thereof by encoding an address line, namely, a word line of its memory cell array wherein the same or matching bit sequence is recorded.
Therefore, by memorizing communication log data in the CAM at addresses associated with their time stamps, for example, a time stamp of a specific communication log can be searched by accessing the CAM with a bit sequence corresponding to log data to be searched.
There may be more than one address line, however, wherein the same data are recorded in the CAM array. Hence, there is usually provided a priority address encoder in the CAM, which outputs a searched address by encoding an address line selected with a certain priority, that is, a lowest address line or a highest address line among address lines of the CAM array which are made active by the search key.
Further, in some CAM devices, there is provided a priority restriction circuit for restricting an effective address range of the address lines to be encoded with the priority by designating a restriction address, so that the priority encoder outputs an address of the lowest address line not lower than the restriction address, or an address of the highest address line not higher than the restriction address, among the address lines made active by the search key.
An example of a CAM provided with such a searching apparatus having the priority encoder and the priority restriction circuit is described by the present inventor in a Japanese patent application entitled "ATM Cell Transfer System" (hereafter called the first prior art), laid open as a Provisional Publication No. 139741/97. In the ATM cell transfer system, by associating addresses of the CAM with timings, address data of received ATM cells stored in a buffer memory are registered in lowest available addresses (corresponding to earliest timings) of the CAM searched with a search key for searching available addresses with the restriction addresses associated with timings (that is, after the timings) at which the received ATM cells are ideally to be transmitted. Such operation enables a prompt and simple re-timing of ATM cells to be transferred.
In another Japanese patent application laid open as a Provisional Publication No. 189979/93 (to be called the second prior art), a different type of the searching apparatus is disclosed, wherein an addresses of a CAM having the matching data are output sequentially one by one with a priority.
However, there are cases wherein a CAM having a limited memory space is desired to be used cyclically.
For example, there may be a case where specific log data earliest after 22 o'clock of the previous date are desired to be searched from communication log data daily recorded at every second in a CAM such that 60.times.60.times.24 addresses are associated to every second of one day. In this case, designating a restriction address corresponding to 22 o'clock, the CAM is searched with a bit sequence corresponding to the specific log data. However, when there is no matching log data found after the restriction address until the highest address, that is, from 22 o'clock to 24 o'clock, the CAM should be searched once more, resetting the restriction address to the lowest address representing 0 o'clock of the present day, as prior art.
It is the same in the second prior art.